package sort;

import java.util.*;

/**
 * 图的深度优先遍历
 */
public class GraphDFS {
    private int[][] adjacencyMatrix; // 邻接矩阵
    private int numVertices; // 顶点数量

    // 构造函数
    public GraphDFS(int numVertices) {
        this.numVertices = numVertices;
        this.adjacencyMatrix = new int[numVertices][numVertices];
    }

    // 添加边
    public void addEdge(int source, int destination) {
        adjacencyMatrix[source][destination] = 1;
        adjacencyMatrix[destination][source] = 1; // 如果是无向图，需要添加反向边
    }

    // 深度优先遍历的递归实现
    private void dfsUtil(int vertex, boolean[] visited) {
        visited[vertex] = true; // 标记当前顶点为已访问
        System.out.print(vertex + " "); // 访问当前顶点

        // 遍历所有顶点，找到当前顶点的邻接顶点
        for (int i = 0; i < numVertices; i++) {
            if (adjacencyMatrix[vertex][i] == 1 && !visited[i]) {
                dfsUtil(i, visited); // 递归访问邻接顶点
            }
        }
    }

    // 深度优先遍历
    public void dfs(int start) {
        boolean[] visited = new boolean[numVertices]; // 用于记录已访问的顶点
        dfsUtil(start, visited); // 从起始顶点开始进行DFS
    }

    public static void main(String[] args) {
        // 创建一个图，包含6个顶点
        GraphDFS graph = new GraphDFS(6);

        // 添加边
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(4, 5);

        System.out.println("深度优先遍历结果：");
        graph.dfs(0); // 从顶点0开始进行DFS
    }
}
